Benson's algorithm
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set".cite-ref-benson-1-0[1] The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.cite-ref-lohne-2-0[2]
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Idea of algorithm
Consider a vector linear program
min C P x subject to A x ≥ ≥ b {\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}
for P ∈ ∈ R q × × n {\displaystyle P\in \mathbb {R} ^{q\times n}} , A ∈ ∈ R m × × n {\displaystyle A\in \mathbb {R} ^{m\times n}} , b ∈ ∈ R m {\displaystyle b\in \mathbb {R} ^{m}} and a polyhedral convex ordering cone C {\displaystyle C} having nonempty interior and containing no lines. The feasible set is S = { x ∈ ∈ R n : A x ≥ ≥ b } {\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}} . In particular, Benson's algorithm finds the extreme points of the set P [ S ] + C {\displaystyle P[S]+C} , which is called upper image.cite-ref-lohne-2-1[2]
In case of C = R + q := { y ∈ ∈ R q : y 1 ≥ ≥ 0 , … … , y q ≥ ≥ 0 } {\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}} , one obtains the special case of a multi-objective linear program (multiobjective optimization).
Dual algorithm
Implementations
Bensolve - a free VLP solver
• www.bensolve.org
Inner
• Link to github
References
cite-note-ehrgottl-hne2011-33. ↑ citerefehrgottl-hneshao2011Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.